/**
 * 142. 环形链表 II
 */
public class Solution_142 {
    /*
      思路：
      将链表分为两段：无环段长度为 a，环段长度为 b。
      当快慢指针相遇时，设慢指针走了 x 步，则快指针走了 2x 步
      那么 2x - x = kb （k为正整数）
      即 x = kb

      那么 慢指针再走 a 步，就可以恰好到达环的起点
      因为 x + a = a + kb
      正好够从起点出发，走一段无环（a），再走 k 圈环段

      此时在起点处设置一个指针 p，让 p 与慢指针 slow 一起走，
      走了 a 步后将会在环的起点处相遇，即得到环的起点
    */
    public ListNode detectCycle(ListNode head) {
        // 快慢指针
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            // 快慢指针相遇，说明链表有环
            if (fast == slow) {
                // 此时 slow 距离环的起点的距离恰好是 a
                ListNode p = head;
                while (p != slow) {
                    slow = slow.next;
                    p = p.next;
                }
                // slow 与 p 相遇的位置一定是环的起点
                return slow;
            }
        }
        // 链表无环，返回 null
        return null;
    }

    public static void main(String[] args) {
        Solution_142 solution = new Solution_142();
        ListNode head = new ListNode(3);
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(0);
        ListNode node3 = new ListNode(-4);
        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node1;
        ListNode ans = solution.detectCycle(head);
        // 这里重写了 ListNode 类的 toString() 方法，只输出 val
        System.out.println(ans);
    }
}
